// Package _3_机器人的运动范围 main
// @Title _3_机器人的运动范围
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-12 18:12
// @Create  2022-01-12 18:12
package main

/**

我们将行坐标和列坐标数位之和大于 k 的格子看作障碍物，那么这道题就是一道很传统的搜索题目，我们可以使用广度优先搜索或者深度优先搜索来解决它，本文选择使用广度优先搜索的方法来讲解

同时这道题还有一个隐藏的优化：我们在搜索的过程中搜索方向可以缩减为向右和向下，而不必再向上和向左进行搜索

*/
func main() {

}

func movingCount(m int, n int, k int) int {
	vis := make([][]bool, m) // 创建二维感染数组
	for i, _ := range vis {
		vis[i] = make([]bool, n) // 初始化为0
	}
	return dfs(0, 0, m, n, k, vis)
}

func dfs(i, j, m, n, k int, vis [][]bool) int {
	if i < 0 || i >= m || j < 0 || j >= n || (i/10+i%10+j/10+j%10) > k || vis[i][j] {
		return 0
	}
	vis[i][j] = true
	return dfs(i+1, j, m, n, k, vis) + dfs(i-1, j, m, n, k, vis) +
		dfs(i, j+1, m, n, k, vis) + dfs(i, j-1, m, n, k, vis) + 1
}
